package Exams.Unity;

import CommonClass.TreeNode;

import java.util.*;

public class q3 {
    class Node {
        int parentIndex;
        int currentIndex;
        int flag;// 0:左孩子 1：右孩子
        TreeNode currentNode;

        public Node(int parentIndex, int currentIndex, int flag, TreeNode currentNode) {
            this.parentIndex = parentIndex;
            this.currentIndex = currentIndex;
            this.flag = flag;
            this.currentNode = currentNode;
        }
    }

    /*
    循环右移二叉树
    https://acm.nowcoder.com/questionTerminal/dd954e299e534af3986a73f98dbdd8a7?orderByHotValue=1&page=1&onlyReference=false
     */
    public TreeNode cyclicShiftTree(TreeNode root, int k) {
        // write code here
        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(0, 0, 0, root));
        int parentNum = 1, nextNum = 0;
        ArrayList<Node> temp_list = new ArrayList<>();
        while (queue.size() != 0) {
            Node node = queue.poll();
            temp_list.add(node);
            --parentNum;
            if (node.currentNode.left != null) {
                queue.offer(new Node(node.currentIndex, nextNum++, 0, node.currentNode.left));
            }
            if (node.currentNode.right != null) {
                queue.offer(new Node(node.currentIndex, nextNum++, 1, node.currentNode.right));
            }
            if (parentNum == 0) {
                parentNum = nextNum;
                nextNum = 0;
                list.add(temp_list);
                temp_list = new ArrayList<>();
            }
        }
        int deep = list.size() - 1;
        for (int i = deep; i >= 1; --i) {
            ArrayList<Node> parent_list = list.get(i - 1);
            int parent_level_sum = parent_list.size();
            for (Node node : parent_list) {
                node.currentNode.left = null;
                node.currentNode.right = null;
            }
            int move = k % (2 * parent_level_sum);
            temp_list = list.get(i);
            for (Node node : temp_list) {
                int target_parent_location = node.flag == 0 ?
                        (node.parentIndex + move / 2) % parent_level_sum : (node.parentIndex + (move + 1) / 2) % parent_level_sum;
                int target_child_flag = node.flag == 0 ? move % 2 : (move + 1) % 2;
                Node parentNode = parent_list.get(target_parent_location);
                if (target_child_flag == 0) parentNode.currentNode.left = node.currentNode;
                else parentNode.currentNode.right = node.currentNode;
            }
        }

        return root;
    }
}
